// 6.46 编写复制一棵二叉树的非递归算法。
#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\5TREE\1_bin_tree\creat.h"

// 递归
void fun_6_46_1(tree *root1, tree *&root2)
{
    if (root1)
    {
        root2 = (tree *)malloc(sizeof(tree));
        root2->data = root1->data;
        root2->left = root2->right = NULL;
        fun_6_46_1(root1->left, root2->left);
        fun_6_46_1(root1->right, root2->right);
    }
}
// 非递归
void fun_6_46_2(tree *root1, tree *&root2)
{
    if (root1)
    {
        tree *que[100];
        tree *que2[100];
        int front, rear;
        front = rear = 0;
        que[rear] = root1;
        root2 = (tree *)malloc(sizeof(tree));
        root2->data = root1->data;
        root2->left = root2->right = NULL;
        que2[rear++] = root2;
        while (front < rear)
        {
            tree *t = que[front];
            tree *r2 = que2[front++];
            if (t->left)
            {
                que[rear] = t->left;
                r2->left = (tree *)malloc(sizeof(tree));
                r2->left->data = t->left->data;
                r2->left->left = r2->left->right = NULL;
                que2[rear++] = r2->left;
            }
            if (t->right)
            {
                que[rear] = t->right;
                r2->right = (tree *)malloc(sizeof(tree));
                r2->right->data = t->right->data;
                r2->right->left = r2->right->right = NULL;
                que2[rear++] = r2->right;
            }
        }
    }
}
int main()
{
    /*******************code*******************/
    int n = 15;
    int a1[15] = {1,
                  2, 3,
                  4, 5, NULL, NULL,
                  NULL, 6, 7, NULL, NULL, NULL, NULL, NULL};
    tree *root;
    CreatTree(root, a1, n, 0);
    tree *root2 = NULL;
    fun_6_46_1(root, root2);
    tree *root3 = NULL;
    fun_6_46_2(root, root3);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
